A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn relatively far apart. The fundamental question concerning proximity drawability is: Given a graph G and a definition of proximity, is it possible to construct a proximity drawing of G? We consider this question for outerplanar graphs with respect to an infinite family of proximity drawings called \beta-drawings. These drawings include as special cases the well-known Gabriel drawings (when \beta =1), and relative neighborhood drawings (when \beta =2). We first show that all biconnected outerplanar graphs are \beta -drawable for all values of \beta such that 1 \le \beta \le 2. As a side effect, this result settles in the affirmative a conjecture by Lubiw and Sleumer, that any biconnected outerplanar graph admits a Gabriel drawing. We than show that there exist biconnectedouterplanar graphs that do not admit any convex \beta -drawing for 1 \le \beta \le 2. We also provide upper bounds on the maximum nuber of biconnected components sharing the same cut-vertex in a \beta -drawable connected outerplanar graphs. This last result is generalized to arbitrary connected planar graphs and is the first non-trivial characterization of connected \beta -drawable graphs. Finally, a weaker definition of proximity drawings is applied and we show that all connected outerplanar graphs are drawable under this definition.
展开▼
机译:图的邻近度绘制是这样一种图,其中根据某种邻近度度量将相邻的顶点对相对靠近地绘制,而成对的非相邻顶点则相距相对远。有关接近可绘制性的基本问题是:给定图形G和接近的定义,是否可以构造G的接近图?我们针对与称为\ beta-drawings的无限近邻图族有关的外平面图考虑此问题。作为特殊情况,这些图包括众所周知的加百利图(当\ beta = 1时)和相对邻域图(当\ beta = 2时)。我们首先显示出,对于所有\ beta值,所有双向连通的外平面图都是\ beta-可绘制的,因此1 \ le \ beta \ le2。作为副作用,该结果肯定是由Lubiw和Sleumer猜想得出的,即任何双向连接的外平面图允许使用Gabriel图。然后,我们证明存在存在双连通外平面图,它们不容许1 \ le \ beta \ le 2的任何凸\ beta绘制。我们还提供了\ beta中共享相同切割顶点的双向互连组件的最大数的上限。 -可绘制的连通外平面图。最后的结果被推广到任意连接的平面图,并且是连接的\ beta可绘制图的第一个非平凡的表征。最后,应用了较弱的接近度图定义,并且我们显示了在此定义下所有连通的外平面图都是可绘制的。
展开▼